package com.computer.fundamentals.algorithm;

/**
 * 经典题目——正则表达式匹配
 * -----------------------------------------------------------------------------------------
 * 给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
 *  '.' 匹配任意单个字符
 *  '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。
 *
 * 示例1：
 * 输入：s = "aa" p = "a"
 * 输出：false
 * 解释："a" 无法匹配 "aa" 整个字符串。
 *
 * 示例2：
 * 输入：s = "aab" p = "c*a*b"
 * 输出：true
 * 解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
 * -----------------------------------------------------------------------------------------
 */
public class RegularExpressionMatching {

    /**
     * 解决方案：
     *  方案一：动态规划
     *      定义动态规划数组dp[i][j], 表示s的前i个字符是否与p的前j个字符匹配, 根据s[i]和p[j]的一个匹配情况，分为
     *      1. 如果s[i] == p[j] 或者 p[j] == '.', 那么dp[i][j] = dp[i-1][j-1]
     *      2. 如果s[i]和p[j]不匹配, 且p[j] == '*' 那么会有两种情况
     *          ① s[i]和p[j-1]能匹配, 那么dp[i][j] = dp[i-1][j](即跳过s[i]这一字符) || dp[i][j-2](即忽略p[j-1]这一字符)
     *          ② s[i]和p[j-1]不能匹配, 那么dp[i][j] = dp[i][j-2]
     */
    public boolean solution(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 1;i <= n;i++) {
            if (p.charAt(i-1) == '*') {
                dp[0][i] = dp[0][i-2];
            }
        }
        for (int i = 1;i <= m;i++) {
            for (int j = 1; j <= n;j++) {
                if (p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i][j-2]; // 题目假定*是有效的，所以此处不用考虑边界问题
                    if (matches(s, p, i, j-1)) {
                        dp[i][j] |= dp[i-1][j];
                    }
                }else {
                    if (matches(s, p, i, j)) {
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        return s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.';
    }

    public static void main(String[] args) {
        RegularExpressionMatching regularExpressionMatching = new RegularExpressionMatching();
        boolean res = regularExpressionMatching.solution("aab", "c*a*b");
        System.out.println(res);
    }
}